
/*
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * SPDX-License-Identifier: GPL-3.0+
 * License-Filename: LICENSE
 * Copyright tuxsee authors
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "splay-tree.h"
#include "main.h"
#include "options.h"
#include "nes.h"
#include "uniqnode.h"
#include "uniqnodeid.h"
#include "uniqstring.h"
#include "folding.h"

/* optional extra level spreading vertical (0/1) */
int levelextra = 0;

/* number of levels in the graph [0...n] */
int maxlevel = 0;

/* number of levels int the graph [1...n] */
int nlevels = 0;

/* initial subgraph folding, 0=as-in-input-specified */
int settings_init_folded = 0;

/* number of summary nodes */
static int n_input_sumnodes = 0;

/* dfs spanning */
static int span = 0;

/* dfs start level */
int dfsstartlevel = 0;

/* reorganize nodes list */
static void folding_reorgn(void);

/* copy edge with optional modifications */
static void folding_cpedge(struct uedge *ue, struct unode *nfn, struct unode *ntn);

/* find nearest subgraph with visible summary node */
static struct usubg *folding_scandown(struct usubg *subg);

/* clear folding control bits */
static void folding_clearbits_subg(struct usubg *subg);

/* clear folding control bits */
static void folding_clearbits(void);

/* main of subgraph folding */
static void subfolding(void);

/* */
static void subfolding_subg(struct usubg *subg);

/* */
static void revedges(void);

/* */
static int revedges_un(struct unode *un, struct uedge *uu);

/* */
void folding_clear(void)
{

	/* clear node id database */
	uniqnodeid_clear();

	/* clear virtual node list and virtual nodes itself */
	virtualnl_clear();

	/* clear virtual edge list and virtual edges itself */
	virtualel_clear();

	/* clear working node list */
	parsedwnl_clear();

	/* clear working edge list */
	parsedwel_clear();

	/* number of levels in the graph */
	maxlevel = 0;

	/* number of levels int the graph [1...n] */
	nlevels = 0;

	/* initial subgraph folding, 0=as-in-input-specified */
	settings_init_folded = 0;

	/* dfs spanning */
	span = 0;

	/* dfs start level */
	dfsstartlevel = 0;

	/* cycles in folded graph determined in folding() */
	n_folded_cycles = 0;

	/* cycles in folded graph after reverse edges determined in folding() (should be 0) */
	n_folded_cycles_revedges = 0;

	/* number of reversed edges */
	n_input_revedges = 0;

	return;
}

/* main of graph folding */
void folding(void)
{
	struct usubg *fromsubg = NULL;
	struct usubg *tosubg = NULL;
	splay_tree_node spn = (splay_tree_node) 0;
	splay_tree_node spn2 = (splay_tree_node) 0;
	struct unode *un = (struct unode *)0;
	struct uedge *ue = (struct uedge *)0;
	int todon = 0;
	int todoe = 0;
	int invisn = 0;
	int visn = 0;

	/* cycles in folded graph determined in folding() */
	n_folded_cycles = 0;

	/* cycles in folded graph after reverse edges determined in folding() (should be 0) */
	n_folded_cycles_revedges = 0;

	if (option_parsedebug) {
		printf("%s(): node data is %d\n", __FUNCTION__, splay_tree_has_data(sp_parsednl));
		fflush(stdout);
	}

	if (option_ldebug) {
		printf("%s(): building working lists\n", __FUNCTION__);
		fflush(stdout);
	}

	/* build work nl and el and sg */
	folding_build_wl();

	if (option_ldebug) {
		printf("%s(): clear folding bits\n", __FUNCTION__);
		fflush(stdout);
	}

	/* clear folding bits done+visible in working sg */
	folding_clearbits();

	if (option_ldebug) {
		printf("%s(): building root lists\n", __FUNCTION__);
		fflush(stdout);
	}

	/* re-build node+edge lists in root/subgraph and create rootnl+rootel */
	rebuild_subg_nel();

	if (option_ldebug) {
		printf("%s(): scanning subgraphs\n", __FUNCTION__);
		fflush(stdout);
	}

	/* fold subgraphs if any */
	if (splay_tree_has_data(sp_parsedsgl)) {
		/* main of subgraph folding */
		subfolding();
	}

	/* all nodes+edges+subgraph may now have done+visibility bit set depending on folding. */

	/*
	 * at this point:
	 * sp_rootnl has work nodes in rootgraph
	 * sp_rootel has work edges in rootgraph
	 * sp_parsedwsgl has work subgraphs in root graph
	 * sg->sp_wsg has work subgraphs in subgraphs
	 * sp_parsedwnl has work nodes
	 * sp_parsedwel has work edges
	 * sg->sp_nl has work nodes in subgraphs
	 * sg->sp_el has work edges in subgraphs
	 * sp_summarynl has summary nodes of subgraphs created during parse()
	 * sp_virtualnl will be filled with temporary dummy nodes
	 * sp_virtualel will be filled with temporary artificial edges created when changing edge in multiple paths
	 */

	if (option_ldebug) {
		printf("%s(): checking todo bits\n", __FUNCTION__);
		fflush(stdout);
	}

	/* nodes/edges/subgraphs have visibility bits set/unset and done set/unset. count. */
	todon = 0;
	todoe = 0;
	invisn = 0;
	visn = 0;

	spn = splay_tree_min(sp_parsedwnl);

	while (spn) {
		un = (struct unode *)spn->value;

		/* check if node is processed */
		switch ((int)un->bitflags.done) {
		case 0:
			/* no, one more node todo. */
			todon = (todon + 1);
			break;
		case 1:
			/* node is checked, see if visible */
			if (un->bitflags.visible == 1) {
				/* visible node */
				visn = (visn + 1);
			} else {
				/* node is skipped because invisible */
				invisn = (invisn + 1);
			}
			break;
		default:
			printf("%s(): bitvalue %d cannot happen\n", __FUNCTION__, (int)un->bitflags.done);
			fflush(stdout);
			break;
		}

		spn = splay_tree_successor(sp_parsedwnl, spn->key);
	}

	if (option_ldebug) {
		printf("%s(): checking summary nodes\n", __FUNCTION__);
		fflush(stdout);
	}

	/* copy summary nodes as working data */
	if (splay_tree_has_data(sp_summarynl)) {

		spn = splay_tree_min(sp_summarynl);

		while (spn) {
			un = (struct unode *)spn->value;

			/* check if node is processed */
			if (un->bitflags.done == 0) {
				/* no, one more node todo. */
				todon = (todon + 1);
			} else {
				/* node is checked, see if visible */
				if (un->bitflags.visible == 1) {
					/* visible node */
					visn = (visn + 1);
				} else {
					/* node is skipped because invisible */
					invisn = (invisn + 1);
				}
			}

			spn = splay_tree_successor(sp_summarynl, spn->key);
		}

	}			/* if(splay_has_data()... */

	if (option_gdebug > 1) {
		printf("%s(): now %d visible nodes %d invisible nodes and %d nodes todo (should be 0)\n", __FUNCTION__, visn,
		       invisn, todon);
		fflush(stdout);
	}

	/* copy edges */
	todoe = 0;

	if (option_ldebug) {
		printf("%s(): expand edgelabels and selfedges\n", __FUNCTION__);
		fflush(stdout);
	}

	/* scan work edges and expand edgelabels and selfedges */
	spn = splay_tree_min(sp_parsedwel);

	while (spn) {
		ue = (struct uedge *)spn->value;

		if (option_ldebug > 1) {
			fprintf(stdout, "edge %d %s->%s\n", ue->number, ue->fn->name, ue->tn->name);
			mghexdump(stdout, (unsigned char *)ue, (unsigned long)sizeof(struct uedge));
			fflush(stdout);
		}

		if ((ue->bitflags.done == 1) && (ue->bitflags.visible == 1)) {
			/* add processed visible internal edges */
			folding_cpedge(ue, NULL, NULL);
			ue->bitflags.done = 1;
		} else if ((ue->bitflags.done == 0) && ((ue->fn->bitflags.visible == 1) && (ue->tn->bitflags.visible == 1))) {
			/* include visible edges which crosses subgraph boundaries */
			ue->bitflags.visible = 1;
			folding_cpedge(ue, NULL, NULL);
			ue->bitflags.done = 1;
		} else {
			if (ue->bitflags.done == 0) {
				todoe = (todoe + 1);
			}
		}

		/* next work edge */
		spn = splay_tree_successor(sp_parsedwel, spn->key);
	}

	/* */
	if (option_ldebug > 1) {
		printf("%s(): %d edges left todo\n", __FUNCTION__, todoe);
		fflush(stdout);
	}

	if (option_ldebug) {
		printf("%s(): checking edge todo bits\n", __FUNCTION__);
		fflush(stdout);
	}

	/* more edges todo */
	if (todoe) {
		/* handle the edges crossing subgraph boundaries */
		spn = splay_tree_min(sp_parsedwel);

		while (spn) {
			ue = (struct uedge *)spn->value;

			/* scan for edges not done yet */
			if (ue->bitflags.done == 0) {
				if ((ue->fn->bitflags.visible == 1) && (ue->tn->bitflags.visible == 1)) {
					/* both visible already handled */
					printf("%s(): shouldnothappen\n", __FUNCTION__);
					fflush(stdout);
					ue->bitflags.done = 1;
				} else if ((ue->fn->bitflags.visible == 1) && (ue->tn->bitflags.visible == 0)) {
					/* from visible and to not visible */
					ue->bitflags.visible = 1;
					tosubg = folding_scandown(ue->tn->rootedon);
					/* change edge and replace to with summaryn-to */
					folding_cpedge(ue, NULL, tosubg->summaryn);
					ue->bitflags.done = 1;
				} else if ((ue->fn->bitflags.visible == 0) && (ue->tn->bitflags.visible == 1)) {
					/* from not visible and to visible */
					ue->bitflags.visible = 1;
					fromsubg = folding_scandown(ue->fn->rootedon);
					/* change edge and replace from with summaryn-from */
					folding_cpedge(ue, fromsubg->summaryn, NULL);
					ue->bitflags.done = 1;
				} else if ((ue->fn->bitflags.visible == 0) && (ue->tn->bitflags.visible == 0)) {
					/* from not visible and to not visible */
					if (ue->fn->rootedon /*->rootsubgraph*/  == ue->tn->rootedon /*->rootsubgraph*/ ) {
						/* from and to are inside same starting subgraph at root */
						ue->bitflags.visible = 0;
						ue->bitflags.done = 1;
					} else {
						/* edge crosses root subgraphs */
						ue->bitflags.visible = 1;
						fromsubg = folding_scandown(ue->fn->rootedon);
						tosubg = folding_scandown(ue->tn->rootedon);
						if (fromsubg->summaryn == tosubg->summaryn) {
							ue->bitflags.visible = 0;
						} else {
							/* change edge and replace from/to with summaryn-from/summaryn-to */
							folding_cpedge(ue, fromsubg->summaryn, tosubg->summaryn);
						}
						ue->bitflags.done = 1;
					}
				} else {
					printf("%s(): shouldnothappen\n", __FUNCTION__);
					fflush(stdout);
					ue->bitflags.done = 1;
				}
			}

			/*
			 * update here:
			 * if ue->visible==0
			 * remove from parsedwel
			 */

			/* next work edge */
			spn = splay_tree_successor(sp_parsedwel, spn->key);
		}
	}

	if (option_ldebug) {
		printf("%s(): build part of edge data\n", __FUNCTION__);
		fflush(stdout);
	}

	/* handle the edges crossing subgraph boundaries */
	spn = splay_tree_min(sp_parsedwel);

	while (spn) {
		/* next work edge */
		spn2 = splay_tree_successor(sp_parsedwel, spn->key);
		ue = (struct uedge *)spn->value;

		if (option_ldebug) {
			printf("%s(): visible=%d at edge %s->%s reversed=%d\n", __FUNCTION__, (int)ue->bitflags.visible,
			       ue->fn->name, ue->tn->name, (int)ue->bitflags.reversed);
			fflush(stdout);
		}

		if (ue->bitflags.visible == 0) {

			if (option_ldebug) {
				printf("%s(): deleting edge %s->%s\n", __FUNCTION__, ue->fn->name, ue->tn->name);
				fflush(stdout);
			}

			splay_tree_remove(sp_parsedwel, (splay_tree_key) ue->number);
		}

		spn = spn2;
	}

	/* create part-of-edge list in all nodes */
	rebuild_poe();

	if (option_ldebug) {
		printf("%s(): re-organize nodes lists\n", __FUNCTION__);
		fflush(stdout);
	}

	/* reorganize nodes list */
	folding_reorgn();

	if (option_ldebug) {
		printf("%s(): revert edges\n", __FUNCTION__);
		fflush(stdout);
	}

	/* rev edges to remove cycles from the graph */
	revedges();

	if (n_folded_cycles) {
		/* edges changed. */
		rebuild_poe();
	}

	if (option_ldebug || 0) {
		printf("%s(): %d reversed edges\n", __FUNCTION__, n_folded_cycles);
		fflush(stdout);
	}

	if (option_ldebug) {
		printf("%s(): ready\n", __FUNCTION__);
		fflush(stdout);
	}

	/* after this the nodes are put in relative vertical levels */
	return;
}

/* */
static void folding_build_wsgl(struct usubg *subg)
{
	splay_tree_key k = (splay_tree_key) 0;
	splay_tree_node spn = (splay_tree_node) 0;
	struct usubg *sg = (struct usubg *)0;

	if (subg == (struct usubg *)0) {
		printf("%s(): nil subg should not happen\n", __FUNCTION__);
		fflush(stdout);
		return;
	}

	/* make sure work list is empty */
	subg->sp_wsg = splay_tree_delete(subg->sp_wsg);

	if (subg->sp_sg) {

		spn = splay_tree_min(subg->sp_sg);

		while (spn) {
			k = (splay_tree_key) spn->key;
			sg = (struct usubg *)spn->value;

			if (sg == (struct usubg *)0) {
				printf("%s(): nil sg should not happen\n", __FUNCTION__);
				fflush(stdout);
				splay_tree_remove(subg->sp_sg, k);
				spn = splay_tree_successor(subg->sp_sg, k);
				continue;
			}

			/* check if to skip this subgraph */
			if (sg->bitflags.skip) {
				spn = splay_tree_successor(subg->sp_sg, k);
				continue;
			}

			/* copy into work list */
			if (subg->sp_wsg == (splay_tree) 0) {
				subg->sp_wsg = splay_tree_new(splay_tree_compare_ints, NULL, NULL);
			}

			splay_tree_insert(subg->sp_wsg, (splay_tree_key) k, (splay_tree_value) sg);

			/* add summarynode of subgraph to work summary node list */
			wsummarynl_add(sg->summaryn);

			/* handle subsubsubgraphs */
			folding_build_wsgl(sg);

			spn = splay_tree_successor(subg->sp_sg, k);
		}

	}

	return;
}

/* build work nl and el */
void folding_build_wl(void)
{
	splay_tree_node spn = (splay_tree_node) 0;
	splay_tree_key k = (splay_tree_key) 0;
	struct unode *un = (struct unode *)0;
	struct uedge *ue = (struct uedge *)0;
	struct usubg *sg = (struct usubg *)0;
	char buf[16];
	char *str = (char *)0;

	/* wipe old work nl and el */
	sp_parsedwnl = splay_tree_delete(sp_parsedwnl);
	sp_parsedwel = splay_tree_delete(sp_parsedwel);
	sp_parsedwsgl = splay_tree_delete(sp_parsedwsgl);
	sp_rootnl = splay_tree_delete(sp_rootnl);
	sp_rootel = splay_tree_delete(sp_rootel);
	sp_wsummarynl = splay_tree_delete(sp_wsummarynl);
	sp_virtualnl = splay_tree_delete(sp_virtualnl);
	sp_virtualel = splay_tree_delete(sp_virtualel);

	/* if no nodes in root or subgraph nothing todo
	 * and put a single node with "empty graph" text on screen
	 */
	if (splay_tree_has_data(sp_parsednl) == 0) {
		if (option_parsedebug) {
			printf("%s(): no node data in parsednl creating empty-graph node\n", __FUNCTION__);
			fflush(stdout);
		}
		memset(buf, 0, 16);
		snprintf(buf, (16 - 1), "__empty%d__", uniq_node_number);
		str = uniqstring(buf);
		un = unode_new(str);
		/* toedoe: this malloc in unode_new() causes memory leak in console mode */
		un->label = uniqstring("empty graph");
		un->utf8label = uniqstring("empty graph");
		/* make this virtual node always visible */
		un->rootedon = NULL;
		un->bitflags.parseerror = 1;
		un->bitflags.edgelabel = 1;
		un->bitflags.visible = 1;
		un->bitflags.done = 1;
		un->bitflags.skip = 0;
		/* make this virtual node to be deleted at next folding() in re-layout */
		un->bitflags.deletenode = 1;
		/* remove any edges if any */
		sp_parsedwel = splay_tree_delete(sp_parsedwel);
		/* insert in parsednl and to be deleted at next re-layout */
		parsednl_add(un);
		parsedwnl_add(un);
		return;
	}

	/* create copy of parsed edges to work on. */
	sp_parsedwsgl = splay_tree_new(	/* The comparision function.  */
					      (splay_tree_compare_fn) splay_tree_compare_ints,
					      /* The deallocate-key function.  NULL if no cleanup is necessary.  */
					      (splay_tree_delete_key_fn) 0,
					      /* The deallocate-value function.  NULL if no cleanup is necessary.  */
					      (splay_tree_delete_value_fn) 0);

	/* in longedges() the uniqnodeid.c builds a db with node-number versus node un struct ptr for reverse search */

	spn = splay_tree_min(sp_parsednl);

	while (spn) {
		k = (splay_tree_key) spn->key;

		/* get node data */
		un = (struct unode *)spn->value;
		/* safety check */
		if (un == (struct unode *)0) {
			printf("%s(): nil un should not happen\n", __FUNCTION__);
			fflush(stdout);
			splay_tree_remove(sp_parsednl, k);
			spn = splay_tree_successor(sp_parsednl, k);
			continue;
		}

		/* default to node is not visible and not done */
		un->bitflags.done = 0;
		un->bitflags.visible = 0;

		/* marked as node to delete at re-layout */
		if (un->bitflags.deletenode) {
			splay_tree_remove(sp_parsednl, k);
			spn = splay_tree_successor(sp_parsednl, k);
			continue;
		}

		/* parse errors are always there */
		if (un->bitflags.parseerror) {
			if (option_parsedebug) {
				printf("%s(): parse error node made visible label `%s'\n", __FUNCTION__, un->label);
				fflush(stdout);
			}
			un->bitflags.done = 1;
			un->bitflags.visible = 1;
		}

		/* nodes in root are always there. */
		if (un->rootedon == NULL) {
			un->bitflags.done = 1;
			un->bitflags.visible = 1;
		}

		/* marked as node to skip at (re)layout */
		if (un->bitflags.skip) {
			un->bitflags.done = 1;
			un->bitflags.visible = 0;
		}

		spn = splay_tree_successor(sp_parsednl, spn->key);
	}

	/* manual copy nodes and optional do not include nodes without connections */
	spn = splay_tree_min(sp_parsednl);

	while (spn) {
		k = (splay_tree_key) spn->key;
		/* get node data */
		un = (struct unode *)spn->value;

		if (option_parsedebug || 0) {
			printf("%s(): name=%s label=%s in=%d out=%d poe=%d level=%d pos=%d\n", __FUNCTION__, un->name, un->label,
			       un->indegree, un->outdegree, splay_tree_has_data(un->sp_poe), un->level, un->pos);
			fflush(stdout);
		}

		/* folding() decides about nodes in subgraphs, check if subgraph is enabled. */
		if (un->rootedon) {
			if (un->rootedon->bitflags.skip) {
				/* subgraph does not exist */
				un->bitflags.done = 1;
				un->bitflags.visible = 0;
				spn = splay_tree_successor(sp_parsednl, k);
				continue;
			}
		}

		/* check if it has no edge connections */
		if ((un->indegree == 0) && (un->outdegree == 0) && (un->rootedon == NULL)) {

			if (option_parsedebug || 0) {
				printf("%s(): found rootgraph singlenode name=%s label=%s\n", __FUNCTION__, un->name, un->label);
				fflush(stdout);
			}

			if (un->bitflags.dummynode) {
				/* skip dummy nodes without edges */
				un->bitflags.done = 1;
				un->bitflags.visible = 0;
				spn = splay_tree_successor(sp_parsednl, k);
				continue;
			}

			/* keep if summary node or parse error message */
			if (un->bitflags.sumnode) {
				/* keep subgraph summary nodes, folding decides on visibility. */
				un->bitflags.done = 0;
				un->bitflags.visible = 0;
				parsedwnl_add(un);
			} else if (un->bitflags.parseerror) {
				/* keep parser error messages always visible */
				un->bitflags.done = 1;
				un->bitflags.visible = 1;
				parsedwnl_add(un);
			} else {
				/* skip other regular single nodes if this option is set */
				if (option_no_singlenodes) {
					un->bitflags.done = 1;
					un->bitflags.visible = 0;
				} else {
					/* add regular single node and optional later on decide on visibility. */
					parsedwnl_add(un);
				}
			}
			/* */
		} else {
			/* this is a node with edge connections. */
			parsedwnl_add(un);
		}

		spn = splay_tree_successor(sp_parsednl, spn->key);
	}

	/* manual copy edges */
	spn = splay_tree_min(sp_parsedel);

	while (spn) {
		k = (splay_tree_key) spn->key;
		ue = (struct uedge *)spn->value;

		/* safety check */
		if (ue == (struct uedge *)0) {
			printf("%s(): nil ue should not happen\n", __FUNCTION__);
			fflush(stdout);
			splay_tree_remove(sp_parsedel, k);
			spn = splay_tree_successor(sp_parsedel, spn->key);
			continue;
		}

		/* set to original back if needed */
		if (ue->bitflags.reversed) {
			un = ue->tn;
			ue->tn = ue->fn;
			ue->fn = un;
			ue->bitflags.reversed = 0;
		}

		/* default to edge is not visible and not done */
		ue->bitflags.done = 0;
		ue->bitflags.visible = 0;
		ue->bitflags.reversed = 0;
		ue->bitflags.longedge = 0;
		ue->bitflags.horedge = 0;

		/* check skip status edge */
		if (ue->bitflags.skip) {
			/* invisble edge to skip */
			ue->bitflags.done = 1;
			ue->bitflags.visible = 0;
			spn = splay_tree_successor(sp_parsedel, spn->key);
			continue;
		}

		/* check line style of edge */
		if (ue->bitflags.style == ESTYLE_INVIS) {
			/* invisble edge to skip */
			ue->bitflags.done = 1;
			ue->bitflags.visible = 0;
			/* XXX todo gcc data test which has invis edge */
#if 1
			spn = splay_tree_successor(sp_parsedel, spn->key);
			continue;
#endif
		}

		/* skip edge if one of the nodes is skipped */
		if ((ue->fn->bitflags.skip) || (ue->tn->bitflags.skip)) {
			ue->bitflags.done = 1;
			ue->bitflags.visible = 0;
			spn = splay_tree_successor(sp_parsedel, spn->key);
			continue;
		}

		/* check if from/to nodes are both in existing subgraphs */
		if (ue->fn->rootedon == NULL) {
			/* from is visible in root graph */
			if (ue->tn->rootedon == NULL) {
				/* to is visible in rootgraph. oke. */
			} else {
				/* to is in subgraph */
				if (ue->tn->rootedon->bitflags.skip) {
					/* to subgraph does not exist. skip this edge. */
					ue->bitflags.done = 1;
					ue->bitflags.visible = 0;
					spn = splay_tree_successor(sp_parsedel, spn->key);
					continue;
				} else {
					/* to subgraph does exist. oke. */
				}
			}
		} else {
			/* from is in subgraph */
			if (ue->fn->rootedon->bitflags.skip) {
				/* from subgraph does not exist. skip edge. */
				ue->bitflags.done = 1;
				ue->bitflags.visible = 0;
				spn = splay_tree_successor(sp_parsedel, spn->key);
				continue;
			} else {
				/* from is in existing subgraph */
				if (ue->tn->rootedon == NULL) {
					/* to is in visible rootgraph. oke. */
				} else {
					/* to is in subgraph */
					if (ue->tn->rootedon->bitflags.skip) {
						/* to subgraph does not exist. skip edge */
						ue->bitflags.done = 1;
						ue->bitflags.visible = 0;
						spn = splay_tree_successor(sp_parsedel, spn->key);
						continue;
					} else {
						/* to subgraph exists. oke. */
					}
				}
			}
		}

		/* check if from/to rooted in same graph */
		if (ue->fn->rootedon == ue->tn->rootedon) {
			/* edge is inside root/subgraph */
			ue->bitflags.insidegraph = 1;
		} else {
			/* edge is crossing graph boundaries */
			ue->bitflags.insidegraph = 0;
		}

		/* check if from/to rooted in rootgraph */
		if ((ue->fn->rootedon == NULL) && (ue->tn->rootedon == NULL)) {
			/* edge in rootgraph is always visible */
			ue->bitflags.done = 1;
			ue->bitflags.visible = 1;
		}

		/* check for self-edge */
		if (ue->fn == ue->tn) {
			/* is a edge "a"->"a" */
			if (option_selfedges) {
				/* add selfedge because option said so. */
				parsedwel_add(ue);
			} else {
				/* skip selfedge because option set to skip them. */
				ue->bitflags.done = 1;
				ue->bitflags.visible = 0;
			}
		} else {
			/* regular edge between different nodes */
			parsedwel_add(ue);
		}

		spn = splay_tree_successor(sp_parsedel, spn->key);
	}

	/* if resulted in no data then insert "empty graph" messsage on screen */
	if (splay_tree_has_data(sp_parsedwnl) == 0) {
		if (option_parsedebug) {
			printf("%s(): no node data in parsedwnl creating empty-graph node\n", __FUNCTION__);
			fflush(stdout);
		}
		memset(buf, 0, 16);
		snprintf(buf, (16 - 1), "__empty%d__", uniq_node_number);
		str = uniqstring(buf);
		un = unode_new(str);
		un->label = uniqstring("empty graph");
		un->utf8label = uniqstring("empty graph");
		/* make this virtual node always visible */
		un->rootedon = NULL;
		un->bitflags.parseerror = 1;
		un->bitflags.edgelabel = 1;
		un->bitflags.visible = 1;
		un->bitflags.done = 1;
		un->bitflags.skip = 0;
		/* make this virtual node to be deleted at next folding() in re-layout */
		un->bitflags.deletenode = 1;
		/* remove any edges if any */
		sp_parsedwel = splay_tree_delete(sp_parsedwel);
		/* insert in parsednl and to be deleted at next re-layout */
		splay_tree_insert(sp_parsednl, (splay_tree_key) un->number, (splay_tree_value) un);
		parsedwnl_add(un);
	}

	/* copy subgraphs */
	if (splay_tree_has_data(sp_parsedsgl)) {

		spn = splay_tree_min(sp_parsedsgl);

		while (spn) {
			k = (splay_tree_key) spn->key;
			sg = (struct usubg *)spn->value;

			if (sg == (struct usubg *)0) {
				printf("%s(): nil sg should not happen\n", __FUNCTION__);
				fflush(stdout);
				splay_tree_remove(sp_parsedsgl, k);
				spn = splay_tree_successor(sp_parsedsgl, k);
				continue;
			}

			/* check if to skip this subgraph */
			if (sg->bitflags.skip) {
				spn = splay_tree_successor(sp_parsedsgl, k);
				continue;
			}

			/* add subgraph to worklist */
			splay_tree_insert(sp_parsedwsgl, (splay_tree_key) k, (splay_tree_value) sg);

			/* add summarynode of subgraph to work summary node list */
			wsummarynl_add(sg->summaryn);

			/* recurse into the subsubsubgraphs */
			folding_build_wsgl(sg);

			spn = splay_tree_successor(sp_parsedsgl, k);
		}

	}

	return;
}

/* reorganize nodes list */
static void folding_reorgn(void)
{
	splay_tree_node spn = (splay_tree_node) 0;
	splay_tree sp_tmp = (splay_tree) 0;
	int c = 0;
	struct unode *un = (struct unode *)0;

	/* sp_parsedwnl is indexed on node number created by parsing order.
	 * now create new sp_parsedwnl indexed and ordered on node in/out degree
	 * first single nodes, then nodes without incoming edges
	 * thejn nodes with in+out edges and final only outgoing edges.
	 */

	sp_tmp = splay_tree_new(splay_tree_compare_ints, NULL, NULL);

	/* number of summary nodes */
	n_input_sumnodes = 0;

	/* if here there are singlenodes in sp_parsedwnl to put at head. */
	spn = splay_tree_min(sp_parsedwnl);

	/* copy singlenodes at head */
	while (spn) {
		un = (struct unode *)spn->value;

		/* single node has no in/out edges, include all */
		if (((un->indegree == 0) && (un->outdegree == 0)) && (un->bitflags.visible == 1)) {

			/* count number of summary nodes */
			if (un->bitflags.sumnode == 1) {
				n_input_sumnodes = n_input_sumnodes + 1;
			}

			/* sumnode is a subgraph summary, parse error is a edgelabel */
			if ((un->bitflags.sumnode == 1) || (un->bitflags.edgelabel == 1)) {
				/* copy this type of single node which must be always there. */
				splay_tree_insert(sp_tmp, (splay_tree_key) c, (splay_tree_value) spn->value);
				c = (c + 1);
			} else {
				/* regular node or dummynode to skip or not */
				if (option_no_singlenodes) {
					/* skip this single node */
				} else {
					/* copy this single node */
					splay_tree_insert(sp_tmp, (splay_tree_key) c, (splay_tree_value) spn->value);
					c = (c + 1);
				}
			}
		}
		spn = splay_tree_successor(sp_parsedwnl, spn->key);
	}

	/* add nodes with no incoming edges */
	spn = splay_tree_min(sp_parsedwnl);

	while (spn) {
		un = (struct unode *)spn->value;
		/* check no in edges */
		if (((un->indegree == 0) && (un->outdegree != 0)) && (un->bitflags.visible == 1)) {
			splay_tree_insert(sp_tmp, (splay_tree_key) c, (splay_tree_value) spn->value);
			c = (c + 1);
		}
		spn = splay_tree_successor(sp_parsedwnl, spn->key);
	}

	/* add nodes with in and out edges */
	spn = splay_tree_min(sp_parsedwnl);

	while (spn) {
		un = (struct unode *)spn->value;
		/* check no in edges */
		if (((un->indegree != 0) && (un->outdegree != 0)) && (un->bitflags.visible == 1)) {
			splay_tree_insert(sp_tmp, (splay_tree_key) c, (splay_tree_value) spn->value);
			c = (c + 1);
		}
		spn = splay_tree_successor(sp_parsedwnl, spn->key);
	}

	/* add nodes with no out edges */
	spn = splay_tree_min(sp_parsedwnl);

	while (spn) {
		un = (struct unode *)spn->value;
		/* check no out edges */
		if (((un->indegree != 0) && (un->outdegree == 0)) && (un->bitflags.visible == 1)) {
			splay_tree_insert(sp_tmp, (splay_tree_key) c, (splay_tree_value) spn->value);
			c = (c + 1);
		}
		spn = splay_tree_successor(sp_parsedwnl, spn->key);
	}

	/* copy result into new sp_parsedwnl */
	splay_tree_delete(sp_parsedwnl);
	sp_parsedwnl = (splay_tree) 0;

	sp_parsedwnl = splay_tree_new(splay_tree_compare_ints, NULL, NULL);

	spn = splay_tree_min(sp_tmp);

	while (spn) {
		splay_tree_insert(sp_parsedwnl, (splay_tree_key) spn->key, (splay_tree_value) spn->value);
		spn = splay_tree_successor(sp_tmp, spn->key);
	}

	sp_tmp = splay_tree_delete(sp_tmp);

	return;
}

/* modify edge which has no basic modifications */
static void folding_cpedge_regular(struct uedge *ue)
{
	struct unode *oldfn = (struct unode *)0;
	struct unode *oldtn = (struct unode *)0;
	struct unode *d1 = (struct unode *)0;
	struct unode *d2 = (struct unode *)0;
	struct unode *d3 = (struct unode *)0;
	struct uedge *ue1 = (struct uedge *)0;
	struct uedge *ue2 = (struct uedge *)0;
	struct uedge *ue3 = (struct uedge *)0;
	struct uedge *ue4 = (struct uedge *)0;

	/* get orig f/t nodes */
	oldfn = ue->fn;
	oldtn = ue->tn;

	if (option_ldebug || 0) {
		printf("%s(): regular edge from %s->%s label \"%s\"\n", __FUNCTION__, oldfn->name, oldtn->name, ue->label);
		fflush(stdout);
	}

	/* check if edge has a label */
	if (ue->label) {
		if (option_ldebug || 0) {
			printf("%s(): checking edge from %s->%s with edge label \"%s\"\n", __FUNCTION__, oldfn->name, oldtn->name,
			       ue->label);
			fflush(stdout);
		}
		/* here at a edge label */
		if ((ue->fn == ue->tn) || (ue->bitflags.selfedge == 1)) {
			if (option_ldebug || 0) {
				printf("%s(): regular self-edge from %s->%s with edge label\n", __FUNCTION__, oldfn->name,
				       oldtn->name);
				fflush(stdout);
			}
			/* replace this selfedge with a loop between dummy nodes */
			d1 = udummynode_new();
			if (option_no_edgelabels) {
				/* skip the label */
				d2 = udummynode_new();
				d2->utf8label = (char *)0;
			} else {
				/* add edge label in self edge */
				d2 = uedgelabel_new(ue->label);
				d2->utf8label = ue->utf8label;
				/* copy text parameters */
				d2->fontname = ue->fontname;
				d2->fontsize = ue->fontsize;
				d2->textcolor = ue->textcolor;
				d2->tx = ue->tx;
				d2->ty = ue->ty;
				d2->bbx = ue->bbx;
				d2->bby = ue->bby;
				d2->bitflags.textbold = ue->bitflags.textbold;
				d2->bitflags.textitalic = ue->bitflags.textitalic;
				d2->bitflags.textoblique = ue->bitflags.textoblique;
				d2->bitflags.txy = ue->bitflags.txy;
			}
			d3 = udummynode_new();
			/* add new nodes as work nodes */
			parsedwnl_add(d1);
			parsedwnl_add(d2);
			parsedwnl_add(d3);
			/* add new nodes as virtual nodes */
			virtualnl_add(d1);
			virtualnl_add(d2);
			virtualnl_add(d3);
			/* new edges between nodes */
			ue1 = uedge_new(oldfn, d1);
			ue2 = uedge_new(d1, d2);
			ue3 = uedge_new(d2, d3);
			ue4 = uedge_new(d3, oldtn);
			/* copy attribs of edges */
			uedge_copy_attribs(ue, ue1);
			uedge_copy_attribs(ue, ue2);
			uedge_copy_attribs(ue, ue3);
			uedge_copy_attribs(ue, ue4);
			/* add edges as work edges */
			parsedwel_add(ue1);
			parsedwel_add(ue2);
			parsedwel_add(ue3);
			parsedwel_add(ue4);
			/* add edges as virtual edges */
			virtualel_add(ue1);
			virtualel_add(ue2);
			virtualel_add(ue3);
			virtualel_add(ue4);
			/* these edges have no edgelabel because they are part of a edge with edgelabel */
			ue1->label = (char *)0;
			ue2->label = (char *)0;
			ue3->label = (char *)0;
			ue4->label = (char *)0;
			/* turn new edges on */
			ue1->bitflags.done = 1;
			ue1->bitflags.visible = 1;
			ue2->bitflags.done = 1;
			ue2->bitflags.visible = 1;
			ue3->bitflags.done = 1;
			ue3->bitflags.visible = 1;
			ue4->bitflags.done = 1;
			ue4->bitflags.visible = 1;
			/* indicate this is a selfedge */
			ue1->bitflags.selfedge = 1;
			ue2->bitflags.selfedge = 1;
			ue3->bitflags.selfedge = 1;
			ue4->bitflags.selfedge = 1;
			/* turn on the nodes */
			oldfn->bitflags.visible = 1;
			oldfn->bitflags.done = 1;
			oldtn->bitflags.visible = 1;
			oldtn->bitflags.done = 1;
			d1->bitflags.visible = 1;
			d1->bitflags.done = 1;
			d2->bitflags.visible = 1;
			d2->bitflags.done = 1;
			d3->bitflags.visible = 1;
			d3->bitflags.done = 1;
			/* turn off old edge */
			ue->bitflags.done = 1;
			ue->bitflags.visible = 0;
		} else {
			/* regular edge if here with edgelabel */

			if (option_ldebug || 0) {
				printf("%s(): regular edge from %s->%s with edge label splitting now\n", __FUNCTION__, oldfn->name,
				       oldtn->name);
				fflush(stdout);
			}

			/* create edgelabel node and route edge */
			d2 = uedgelabel_new(ue->label);
			d2->utf8label = ue->utf8label;
			d2->tx = ue->tx;
			d2->ty = ue->ty;
			d2->bbx = ue->bbx;
			d2->bby = ue->bby;

			/* no edge label */
			if (option_no_edgelabels) {
				d2->label = uniqstring("");
				d2->utf8label = d2->label;
				d2->tx = 0;
				d2->ty = 0;
				d2->bbx = 0;
				d2->bby = 0;
			}

			/* copy text parameters */
			d2->fontname = ue->fontname;
			d2->fontsize = ue->fontsize;
			d2->textcolor = ue->textcolor;
			d2->bitflags.textbold = ue->bitflags.textbold;
			d2->bitflags.textitalic = ue->bitflags.textitalic;
			d2->bitflags.textoblique = ue->bitflags.textoblique;
			d2->bitflags.txy = ue->bitflags.txy;

			/* add as work node */
			parsedwnl_add(d2);

			/* add artificial node */
			virtualnl_add(d2);

			/* create new routing of edges */
			ue1 = uedge_new(oldfn, d2);
			ue2 = uedge_new(d2, oldtn);

			/* copy attributes of edge */
			uedge_copy_attribs(ue, ue1);
			uedge_copy_attribs(ue, ue2);

			/* add as working edges */
			parsedwel_add(ue1);
			parsedwel_add(ue2);
			/* add artificial edges */
			virtualel_add(ue1);
			virtualel_add(ue2);
			/* these edges have no edgelabel because they are part of a edge with edgelabel */
			ue1->label = (char *)0;
			ue2->label = (char *)0;
			/* turn new edges on */
			ue1->bitflags.done = 1;
			ue1->bitflags.visible = 1;
			ue2->bitflags.done = 1;
			ue2->bitflags.visible = 1;
			/* turn off old edge */
			ue->bitflags.done = 1;
			ue->bitflags.visible = 0;
			/* turn on the nodes of this new edge */
			oldfn->bitflags.visible = 1;
			oldfn->bitflags.done = 1;
			oldtn->bitflags.visible = 1;
			oldtn->bitflags.done = 1;
			d2->bitflags.visible = 1;
			d2->bitflags.done = 1;
		}

		return;
	}

	if (option_ldebug || 0) {
		printf("%s(): regular edge from %s->%s without edge label\n", __FUNCTION__, oldfn->name, oldtn->name);
		fflush(stdout);
	}

	/* this is a regular edge without label. check for selfedge */
	if (((ue->fn == ue->tn) || (ue->bitflags.selfedge == 1)) && (ue->bitflags.done == 0)) {
		if (option_ldebug || 0) {
			printf("%s(): regular self-edge from %s->%s without edge label\n", __FUNCTION__, oldfn->name, oldtn->name);
			fflush(stdout);
		}
		/* replace this selfedge with a loop between dummy nodes. no label. */
		d1 = udummynode_new();
		d2 = udummynode_new();
		d3 = udummynode_new();
		parsedwnl_add(d1);
		parsedwnl_add(d2);
		parsedwnl_add(d3);
		virtualnl_add(d1);
		virtualnl_add(d2);
		virtualnl_add(d3);
		/* new edges between nodes */
		ue1 = uedge_new(oldfn, d1);
		ue2 = uedge_new(d1, d2);
		ue3 = uedge_new(d2, d3);
		ue4 = uedge_new(d3, oldtn);
		/* copy attribs of edges */
		uedge_copy_attribs(ue, ue1);
		uedge_copy_attribs(ue, ue2);
		uedge_copy_attribs(ue, ue3);
		uedge_copy_attribs(ue, ue4);
		/* add edges as work edges */
		parsedwel_add(ue1);
		parsedwel_add(ue2);
		parsedwel_add(ue3);
		parsedwel_add(ue4);
		/* add edges as virtual edges */
		virtualel_add(ue1);
		virtualel_add(ue2);
		virtualel_add(ue3);
		virtualel_add(ue4);
		/* turn new edges on */
		ue1->bitflags.done = 1;
		ue1->bitflags.visible = 1;
		ue2->bitflags.done = 1;
		ue2->bitflags.visible = 1;
		ue3->bitflags.done = 1;
		ue3->bitflags.visible = 1;
		ue4->bitflags.done = 1;
		ue4->bitflags.visible = 1;
		/* indicate this is a selfedge */
		ue1->bitflags.selfedge = 1;
		ue2->bitflags.selfedge = 1;
		ue3->bitflags.selfedge = 1;
		ue4->bitflags.selfedge = 1;
		/* turn on the nodes */
		oldfn->bitflags.visible = 1;
		oldfn->bitflags.done = 1;
		oldtn->bitflags.visible = 1;
		oldtn->bitflags.done = 1;
		d1->bitflags.visible = 1;
		d1->bitflags.done = 1;
		d2->bitflags.visible = 1;
		d2->bitflags.done = 1;
		d3->bitflags.visible = 1;
		d3->bitflags.done = 1;
		/* turn off old edge */
		ue->bitflags.done = 1;
		ue->bitflags.visible = 0;
	} else {
		/* this is a edge without label and not selfedge. no modifications. */
		ue->bitflags.done = 1;
		ue->bitflags.visible = 1;
		/* turn on the nodes */
		oldfn->bitflags.visible = 1;
		oldfn->bitflags.done = 1;
		oldtn->bitflags.visible = 1;
		oldtn->bitflags.done = 1;
	}

	return;
}

/*
 * copy edge with optional modifications
 * if option_no_edgelabels is set then edgelabel node is not created
 */
static void folding_cpedge(struct uedge *ue, struct unode *nfn, struct unode *ntn)
{
	struct unode *rfn = (struct unode *)0;
	struct unode *rtn = (struct unode *)0;
	struct uedge *ue1 = (struct uedge *)0;
	struct uedge *ue2 = (struct uedge *)0;
	struct unode *d2 = (struct unode *)0;

	/* 目前红黑树只适合记录引用数 */

	/* check if there are modifications */
	if ((nfn == (struct unode *)0) && (ntn == (struct unode *)0)) {
		/* check for selfedge */
		if ((ue->fn == ue->tn) || (ue->bitflags.selfedge == 1)) {
			/* check if to skip. */
			if (option_selfedges == 0) {
				/* skip selfedge */
				ue->bitflags.done = 1;
				ue->bitflags.visible = 0;
				return;
			}
		}
		/* handle regular edge/selfedge with optional label */
		folding_cpedge_regular(ue);
		return;
	}

	/* check the replacement summary nodes */
	if (nfn == ntn) {
		/* this is a selfedge from subgraph summary node to same subgraph summary node to skip */
		ue->bitflags.visible = 0;
		ue->bitflags.done = 1;
		/* can be changed in a option to turn it on if needed */
		return;
	}

	/* here if a edge with modifications pointing to subgraph summary nodes */

	/* 在销毁红黑树时 */

	/* set modified from and to node */
	rfn = nfn;

	if (rfn == NULL) {
		/* use original from */
		rfn = ue->fn;
	}

	rtn = ntn;

	if (rtn == NULL) {
		/* use original to */
		rtn = ue->tn;
	}

	if (option_ldebug || 0) {
		printf("%s(): edge crossing subgraphs from %s->%s\n", __FUNCTION__, rfn->name, rtn->name);
		fflush(stdout);
	}

	/* 只会释放结点内存 */

	if (ue->label) {
		/* check edge label option */
		if (option_no_edgelabels) {
			/* edge without label */
			/* new edges between nodes */
			ue1 = uedge_new(rfn, rtn);
			/* copy attribs of edges */
			uedge_copy_attribs(ue, ue1);
			/* add edges as work edges */
			parsedwel_add(ue1);
			/* add edges as virtual edges */
			virtualel_add(ue1);
			/* turn new edges on */
			ue1->bitflags.done = 1;
			ue1->bitflags.visible = 1;
			/* turn on the nodes */
			rfn->bitflags.visible = 1;
			rfn->bitflags.done = 1;
			rtn->bitflags.visible = 1;
			rtn->bitflags.done = 1;
		} else {
			/* add edgelabel */
			/* create edgelabel node and route edge */
			d2 = uedgelabel_new(ue->label);
			d2->utf8label = ue->utf8label;
			/* copy text parameters */
			d2->fontname = ue->fontname;
			d2->fontsize = ue->fontsize;
			d2->textcolor = ue->textcolor;
			d2->tx = ue->tx;
			d2->ty = ue->ty;
			d2->bbx = ue->bbx;
			d2->bby = ue->bby;
			d2->bitflags.textbold = ue->bitflags.textbold;
			d2->bitflags.textitalic = ue->bitflags.textitalic;
			d2->bitflags.textoblique = ue->bitflags.textoblique;
			d2->bitflags.txy = ue->bitflags.txy;
			/* add working node */
			parsedwnl_add(d2);
			/* add artificial node */
			virtualnl_add(d2);
			/* create the new edge routing */
			ue1 = uedge_new(rfn, d2);
			ue2 = uedge_new(d2, rtn);
			/* copy the edge attributes */
			uedge_copy_attribs(ue, ue1);
			uedge_copy_attribs(ue, ue2);
			/* add as working edges */
			parsedwel_add(ue1);
			parsedwel_add(ue2);
			/* add as artificial edges */
			virtualel_add(ue1);
			virtualel_add(ue2);
			/* these new edge have no edgelabel because there are part of edgelabel edge */
			ue1->label = (char *)0;
			ue2->label = (char *)0;
			/* turn new edges on */
			ue1->bitflags.done = 1;
			ue1->bitflags.visible = 1;
			ue2->bitflags.done = 1;
			ue2->bitflags.visible = 1;
			/* turn off old edge */
			ue->bitflags.done = 1;
			ue->bitflags.visible = 0;
			/* turn on the nodes */
			rfn->bitflags.visible = 1;
			rfn->bitflags.done = 1;
			rtn->bitflags.visible = 1;
			rtn->bitflags.done = 1;
			d2->bitflags.visible = 1;
			d2->bitflags.done = 1;
		}
	} else {

		/* 不会释放 */

		/* edge without label */
		/* new edges between nodes */
		ue1 = uedge_new(rfn, rtn);
		/* copy attribs of edges */
		uedge_copy_attribs(ue, ue1);
		/* add edges as work edges */
		parsedwel_add(ue1);
		/* add edges as virtual edges */
		virtualel_add(ue1);
		/* turn new edges on */
		ue1->bitflags.done = 1;
		ue1->bitflags.visible = 1;
		/* turn on the nodes */
		rfn->bitflags.visible = 1;
		rfn->bitflags.done = 1;
		rtn->bitflags.visible = 1;
		rtn->bitflags.done = 1;
	}

	/* turn off old edge */
	ue->bitflags.visible = 0;
	ue->bitflags.done = 1;

	/* 结点中记录的数据的内存。 */

	return;
}

/* find lowest and nearest subgraph with visible summary node */
static struct usubg *folding_scandown(struct usubg *subg)
{
	struct usubg *subgptr = NULL;

	subgptr = subg;

	while (subgptr) {
		/* stop at subgraph in root graph */
		if (subgptr->rootedon == NULL) {
			break;
		}
		/* stop at subgraph with visible summary node */
		if (subgptr->summaryn) {
			/* clang issue */
			if (subgptr->summaryn->bitflags.visible == 1) {
				break;
			}
		}
		/* search lower */
		subgptr = subgptr->rootedon;
	}

	/* extra check for visible summary node */
	if (subgptr->summaryn) {
		if (subgptr->summaryn->bitflags.visible == 0) {
			printf("%s(): expected visible summary node at subgraph \"%s\"\n", __FUNCTION__, subgptr->name);
			fflush(stdout);
		}
	}

	/* lowest one */
	return ((struct usubg *)subgptr);
}

/* clear folding control bits */
static void folding_clearbits_subg(struct usubg *subg)
{
	splay_tree_node spn = (splay_tree_node) 0;
	struct usubg *sg = (struct usubg *)0;

	if (subg == NULL) {
		printf("%s(): nil subg\n", __FUNCTION__);
		fflush(stdout);
		return;
	}

	if (option_gdebug) {
		printf("%s(): subgraph \"%s\" folded=%d\n", __FUNCTION__, subg->name, subg->bitflags.folded);
		fflush(stdout);
	}

	/* recurse */
	if (splay_tree_has_data(subg->sp_sg)) {

		spn = splay_tree_min(subg->sp_sg);

		while (spn) {
			sg = (struct usubg *)spn->value;
			folding_clearbits_subg(sg);
			spn = splay_tree_successor(subg->sp_sg, spn->key);
		}
	}

	/* clear this subgraph */
	subg->bitflags.done = 0;
	subg->bitflags.visible = 0;

	subg->summaryn->bitflags.done = 0;
	subg->summaryn->bitflags.visible = 0;

	return;
}

/* clear folding control bits */
static void folding_clearbits(void)
{
	struct usubg *sg = (struct usubg *)0;
	splay_tree_node spn = (splay_tree_node) 0;
	splay_tree_key k = (splay_tree_key) 0;

	/* clear done and visible bit in parsed subgraphs */
	if (splay_tree_has_data(sp_parsedwsgl)) {

		spn = splay_tree_min(sp_parsedwsgl);

		while (spn) {
			k = (splay_tree_key) spn->key;

			sg = (struct usubg *)spn->value;

			if (sg == (struct usubg *)0) {
				printf("%s(): nil sg\n", __FUNCTION__);
				fflush(stdout);
				splay_tree_remove(sp_parsedwsgl, k);
				spn = splay_tree_successor(sp_parsedwsgl, k);
				continue;
			}

			/* clear folding bits in sub and subsub.. */
			folding_clearbits_subg(sg);

			/* */
			spn = splay_tree_successor(sp_parsedwsgl, spn->key);
		}
	}

	return;
}

/* handle folding of subgraph and the sub subsub... */
static void subfolding_subg(struct usubg *subg)
{
	int nlvis = 0;
	int elvis = 0;
	int sumvis = 0;
	int subvis = 0;
	splay_tree_node spn = (splay_tree_node) 0;
	struct usubg *sg = (struct usubg *)0;
	struct uedge *ue = (struct uedge *)0;
	struct unode *un = (struct unode *)0;

	/* check if subgraph is in rootgraph with optional subgraphs. */
	if (subg->rootedon == NULL) {
		if (option_ldebug > 1) {
			printf("%s(): root subgraph \"%s\" folded=%d\n", __FUNCTION__, subg->name, subg->bitflags.folded);
			fflush(stdout);
		}

		/* check folding status of this subgraph */
		if (subg->bitflags.folded == 0) {
			/* visible in rootgraph */
			nlvis = 1;
			elvis = 1;
			sumvis = 0;
			subvis = 1;
		} else {
			/* invisible in rootgraph */
			nlvis = 0;
			elvis = 0;
			sumvis = 1;
			subvis = 0;
		}

	} else {
		/* subgraph in another subgraph */

		if (option_ldebug > 1) {
			printf("%s(): sub subgraph \"%s\" rootedon-visible=%d folded=%d\n",
			       __FUNCTION__, subg->name, subg->rootedon->bitflags.visible, subg->bitflags.folded);
			fflush(stdout);
		}

		if (subg->rootedon->bitflags.visible == 1) {
			/* rooted on a fully visible subgraph */
			/* check folding status of this subgraph */
			if (subg->bitflags.folded == 0) {
				/* visible subgraph */
				nlvis = 1;
				elvis = 1;
				sumvis = 0;
				subvis = 1;
			} else {
				/* invisible subgraph */
				nlvis = 0;
				elvis = 0;
				sumvis = 1;
				subvis = 0;
			}
		} else {
			/* rooted on a invisible subgraph with possible only a summary node */
			nlvis = 0;
			elvis = 0;
			sumvis = 0;
			subvis = 0;
		}
	}

	/* nlvis is nodes are visible */
	if (splay_tree_has_data(subg->sp_nl)) {

		spn = splay_tree_min(subg->sp_nl);

		while (spn) {
			un = (struct unode *)spn->value;

			/* */
			if (un->bitflags.done == 0) {
				un->bitflags.visible = nlvis;
				un->bitflags.done = 1;
			} else {
				printf("%s(): node is already done\n", __FUNCTION__);
				fflush(stdout);
			}
			spn = splay_tree_successor(subg->sp_nl, spn->key);
		}

	}

	/* elvis is internal edges are visible */
	if (splay_tree_has_data(subg->sp_el)) {

		spn = splay_tree_min(subg->sp_el);

		while (spn) {
			ue = (struct uedge *)spn->value;
			if (ue->bitflags.done) {
				printf("%s(): edge is already done\n", __FUNCTION__);
				fflush(stdout);
			} else {
				/* check internal edge */
				if (ue->fn->rootedon == ue->tn->rootedon) {
					/* check inside this subgraph */
					if (ue->fn->rootedon == subg) {
						ue->bitflags.visible = elvis;
						ue->bitflags.done = 1;

						if (ue->bitflags.insidegraph == 0) {
							printf("%s(): edge should have been marked inside graph\n", __FUNCTION__);
							fflush(stdout);
							ue->bitflags.insidegraph = 1;
						}
					} else {
						printf("%s(): shouldnothappen\n", __FUNCTION__);
						fflush(stdout);
					}
				}
			}

			spn = splay_tree_successor(subg->sp_el, spn->key);
		}

	}

	/* sumvis is summarynode-is-visible */
	subg->summaryn->bitflags.visible = sumvis;
	subg->summaryn->bitflags.done = 1;

	/* set summary node as work node */
	if (subg->summaryn->bitflags.visible) {
		parsedwnl_add(subg->summaryn);
	}

	/* subvis is subgraph-is-visible */
	subg->bitflags.visible = subvis;
	subg->bitflags.done = 1;

	/* recurse */
	if (splay_tree_has_data(subg->sp_sg)) {

		spn = splay_tree_min(subg->sp_sg);

		while (spn) {
			sg = (struct usubg *)spn->value;

			/* this is recursive into the deeper subg handle folding of subgraph and the sub subsub... */
			subfolding_subg(sg);

			spn = splay_tree_successor(subg->sp_sg, spn->key);
		}

	}

	return;
}

/* main of subgraph folding */
static void subfolding(void)
{
	struct usubg *sg = (struct usubg *)0;
	splay_tree_node spn = (splay_tree_node) 0;
	splay_tree_key k = (splay_tree_key) 0;

	/* check if something todo. */
	if (splay_tree_has_data(sp_parsedwsgl) == 0) {
		if (option_gdebug > 1) {
			printf("%s(): no work subgraph data\n", __FUNCTION__);
			fflush(stdout);
		}
		return;
	}

	spn = splay_tree_min(sp_parsedwsgl);

	while (spn) {
		k = (splay_tree_key) spn->key;
		sg = (struct usubg *)spn->value;

		/* safety check */
		if (sg == (struct usubg *)0) {
			printf("%s(): nil sg should not happen\n", __FUNCTION__);
			fflush(stdout);
			/* remove this entry to avoid trouble later on */
			splay_tree_remove(sp_parsedwsgl, k);
			spn = splay_tree_successor(sp_parsedwsgl, k);
			continue;
		}

		if (option_gdebug > 1) {
			printf("%s(): subgraph \"%s\" folded=%d\n", __FUNCTION__, sg->name, sg->bitflags.folded);
			fflush(stdout);
		}

		/* handle folding of subgraph and the sub subsub... */
		subfolding_subg(sg);

		/* next subgraph */
		spn = splay_tree_successor(sp_parsedwsgl, spn->key);
	}

	return;
}

/* dfs */
static int revedges_un(struct unode *un, struct uedge *uu)
{
	splay_tree_node spn = (splay_tree_node) 0;
	struct uedge *ue = (struct uedge *)0;
	struct unode *tmpnode = (struct unode *)0;
	int n = 0;

	if (uu) {
	}

	if (un->bitflags.done) {
		return (0);
	}

	un->bitflags.done = 1;
	un->bitflags.dfsgrey = 1;

	/* scan the outgoing edges connected to node */
	if (splay_tree_has_data(un->sp_poe)) {

		/* scan edge list of this node */
		spn = splay_tree_min(un->sp_poe);

		while (spn) {
			ue = (struct uedge *)spn->value;

			/* select outgoing edges */
			if (ue->fn == un) {
				if (ue->tn->bitflags.dfsgrey) {
					/* reverse the edge */
					tmpnode = ue->fn;
					ue->fn = ue->tn;
					ue->tn = tmpnode;

					/* toggle reversed bit */
					if (ue->bitflags.reversed) {
						ue->bitflags.reversed = 0;
					} else {
						ue->bitflags.reversed = 1;
					}
					n++;
				} else {
					/* dive into this outgoing edge */
					if (ue->tn->bitflags.done == 0) {
						n = (n + revedges_un(ue->tn, ue));
					}
				}
			}
			spn = splay_tree_successor(un->sp_poe, spn->key);
		}
	}

	un->bitflags.dfsgrey = 0;

	/* number of reversed edges */
	return (n);
}

static void revedges(void)
{
	splay_tree_node spn = (splay_tree_node) 0;
	struct unode *un = (struct unode *)0;
	struct uedge *ue = (struct uedge *)0;
	int n = 0;
	char *s = NULL;

	/* number of reversed edges */
	n_input_revedges = 0;

	/* cycles in folded graph determined in folding() */
	n_folded_cycles = 0;

	/* cycles in folded graph after reverse edges determined in folding() (should be 0) */
	n_folded_cycles_revedges = 0;

	/* clear done bit in all nodes */
	spn = splay_tree_min(sp_parsedwnl);

	while (spn) {
		un = (struct unode *)spn->value;
		un->bitflags.done = 0;	/* white */
		un->bitflags.dfsgrey = 0;
		spn = splay_tree_successor(sp_parsedwnl, spn->key);
	}

	/* scan the work node list */
	spn = splay_tree_min(sp_parsedwnl);

	while (spn) {
		un = (struct unode *)spn->value;

		/* node is white? */
		if (un->bitflags.done == 0) {
			/* recursive dive */
			n = n + revedges_un(un, NULL);
		}

		spn = splay_tree_successor(sp_parsedwnl, spn->key);
	}

	if (n) {
		if (option_ldebug) {
			printf("%s(): reversed %d edges\n", __FUNCTION__, n);
		}

		if (option_testcode || 0) {
			printf("/* %s(): result after %d reversed edges - red edges are reversed edges */\n", __FUNCTION__, n);
			printf("digraph \"revedges()-result\" {\n");

			spn = splay_tree_min(sp_parsedwel);

			while (spn) {
				ue = (struct uedge *)spn->value;
				if (ue->bitflags.reversed) {
					s = "red";
				} else {
					s = "black";
				}
				printf
				    (" \"%s\"->\"%s\"[color=\"%s\"]; // edge number=[e%d], reversed-status=%d, node number=[n%d]->[n%d]\n",
				     ue->fn->name, ue->tn->name, s, ue->number, ue->bitflags.reversed, ue->fn->number,
				     ue->tn->number);
				spn = splay_tree_successor(sp_parsedwel, spn->key);
			}

			printf("}\n");
		}

	}

	/* make sure the poe lists is rebuilt */
	n_folded_cycles = n;
	n_input_revedges = n;

	return;
}

/* count selfedges at nodes and mark selfedges at edges */
void markselfedges(void)
{
	splay_tree_node spn = (splay_tree_node) 0;
	struct uedge *ue = (struct uedge *)0;
	/* use the initial edge list */
	if (splay_tree_has_data(sp_parsedel)) {

		spn = splay_tree_min(sp_parsedel);
		while (spn) {
			ue = (struct uedge *)spn->value;
			if (ue->fn == ue->tn) {
				/* this is a self edge mark in edge */
				ue->bitflags.selfedge = 1;
				/* update number of selfedges connected at node */
				ue->fn->nse = (ue->fn->nse + 1);
			}

			spn = splay_tree_successor(sp_parsedel, spn->key);
		}

	}

	return;
}

/* indicate single nodes */
void marksinglenodes(void)
{
	splay_tree_node spn = (splay_tree_node) 0;
	struct unode *un = (struct unode *)0;
	struct uedge *ue = (struct uedge *)0;
	/* use the initial edge list */
	if (splay_tree_has_data(sp_parsedel)) {

		spn = splay_tree_min(sp_parsedel);
		while (spn) {
			ue = (struct uedge *)spn->value;
			/* check if selfedge */
			if (ue->bitflags.selfedge == 1) {
				/* selfedges are not counted at in/out degree of node */
				ue->fn->bitflags.selfedge = 1;
			} else {
				/* update in and out degree of nodes */
				ue->fn->outdegree = (ue->fn->outdegree + 1);
				ue->tn->indegree = (ue->tn->indegree + 1);
			}

			spn = splay_tree_successor(sp_parsedel, spn->key);
		}

	}

	/* use the initial node list to mark single nodes in root graph */
	if (splay_tree_has_data(sp_parsednl)) {

		spn = splay_tree_min(sp_parsednl);
		while (spn) {
			un = (struct unode *)spn->value;
			/* check if node has in/out edges */
			if ((un->indegree == 0) && (un->outdegree == 0) && (un->rootedon == NULL)) {
				/* mark node is singlenode without in/out edges but may have selfedges count in nse */
				un->bitflags.singlenode = 1;
				if (option_parsedebug || 0) {
					printf("%s(): found rootgraph singlenode=\"%s\" label=\"%s\" selfedge=%d\n", __FUNCTION__,
					       un->name, un->label, un->bitflags.selfedge);
					fflush(stdout);
				}
			}

			spn = splay_tree_successor(sp_parsednl, spn->key);
		}

	}

	return;
}

/* put nodes in levels */
static void nodesinlevels_un(struct unode *un)
{
	struct uedge *ue = (struct uedge *)0;
	splay_tree_node spn = (splay_tree_node) 0;

	/* check if already handled */
	if (un->bitflags.done) {
		return;
	}

	un->bitflags.done = 1;

	/* set level of this node */
	un->level = span;

	/* update max used level */
	if (un->level > maxlevel) {
		maxlevel = un->level;
	}

	if (option_ldebug || 0) {
		printf("%s(): node \"%s\" is in level %d of %d levels\n", __FUNCTION__, un->name, un->level, maxlevel);
		fflush(stdout);
	}

	/* scan the outgoing edges connected to node */
	if (splay_tree_has_data(un->sp_poe)) {

		spn = splay_tree_min(un->sp_poe);

		while (spn) {
			ue = (struct uedge *)spn->value;

			/* outgoing edge */
			if (ue->fn == un) {
				if (ue->tn->bitflags.done == 0) {
					/* extra +1 to interleave levels with nodes
					 * with levels with dummynodes and longer
					 * edges to improve edge line routing.
					 * same-edges will be expanded automatically.
					 * barycenter will run slower.
					 * cannot be used with centerm draw because it assumes only 1 intermediate level.
					 */
					span = (span + 1 + 1 + levelextra);
					nodesinlevels_un(ue->tn);
					span = un->level;
				}
			}
			spn = splay_tree_successor(un->sp_poe, spn->key);
		}
	}

	return;
}

/* put nodes in levels returns no. of horizontal edges */
int nodesinlevels(void)
{
	splay_tree_node spn = (splay_tree_node) 0;
	splay_tree_node spn2 = (splay_tree_node) 0;
	struct unode *un = (struct unode *)0;
	struct uedge *ue = (struct uedge *)0;
	int he = 0;
	int delta = 0;

	/* no levels in graph */
	maxlevel = 0;

	/* number of levels int the graph [1...n] */
	nlevels = 0;

	/* check if there is data */
	if (splay_tree_has_data(sp_parsedwnl) == 0) {
		return (0);
	}

	/* check if there are single nodes which are put at level 0 if visible via option. */
	if (n_input_singlenodes) {

		/* change start level used in dfs */
		if (option_no_singlenodes) {
			/* no single nodes in drawing, start connected nodes at level 0 */
			dfsstartlevel = 0;
		} else {
			/* start connected nodes at level 1 */
			dfsstartlevel = 1;
		}

	} else {
		/* there are no single nodes, start at 0 */
		dfsstartlevel = 0;
	}

	/* summary nodes on 1st level, expanded graph on next level and more */
	if (n_input_sumnodes) {
		dfsstartlevel = 1;
	}

	/* clear done bit in all nodes */
	spn = splay_tree_min(sp_parsedwnl);

	while (spn) {
		un = (struct unode *)spn->value;

		un->bitflags.done = 0;
		un->level = 0;

		if (option_ldebug || 0) {
			printf("%s(): node number=[n%d] \"%s\" is in parsedwnl startlevel=%d\n", __FUNCTION__, un->number, un->name,
			       dfsstartlevel);
			fflush(stdout);
		}

		spn = splay_tree_successor(sp_parsedwnl, spn->key);
	}

	if (option_ldebug || 0) {

		spn = splay_tree_min(sp_parsedwel);

		printf("%s(): parsedwel=%p spn=%p\n", __FUNCTION__, (void *)sp_parsedwel, (void *)spn);
		fflush(stdout);

		while (spn) {
			ue = (struct uedge *)spn->value;

			if (option_ldebug || 0) {
				printf("%s(): edge \"%s\"->\"%s\" is in parsedwel reversed=%d\n", __FUNCTION__, ue->fn->name,
				       ue->tn->name, (int)ue->bitflags.reversed);
				fflush(stdout);
			}

			spn = splay_tree_successor(sp_parsedwel, spn->key);
		}
	}

	if (option_ldebug || 0) {
		printf("%s(): starting dfs at startlevel %d\n", __FUNCTION__, dfsstartlevel);
		fflush(stdout);
	}

	spn = splay_tree_min(sp_parsedwnl);

	while (spn) {
		un = (struct unode *)spn->value;

		if (un->bitflags.done == 0) {

			/* if node has no edges */
			if (splay_tree_has_data(un->sp_poe) == 0) {
				/* set single node at level 0 */
				span = 0;
			} else {
				/* start connected node at startlevel, not 0 */
				span = dfsstartlevel;
			}

			/* recursive dive */
			nodesinlevels_un(un);
		}

		spn = splay_tree_successor(sp_parsedwnl, spn->key);
	}

	/* tune depth */
	spn = splay_tree_min(sp_parsedwel);

	while (spn) {
		ue = (struct uedge *)spn->value;

		/* check if longer edge */
		delta = ue->tn->level - ue->fn->level;

		if (delta > (1 + 1 + levelextra)) {
			/* if from-node is free to move */
			if ((ue->fn->indegree == 0) && (ue->fn->outdegree == 1)) {
				/* move closer to to-node */
				ue->fn->level = ue->tn->level - (2 + levelextra);
			} else if ((ue->tn->outdegree == 0) && (ue->tn->indegree == 1)) {
				ue->tn->level = ue->fn->level + (2 + levelextra);
			} else {
				/* nodes are not free to move across levels */
			}
		}

		spn = splay_tree_successor(sp_parsedwel, spn->key);
	}

	if (1 /* tweaking */ ) {

		/* check edge label nodes and how it connects.
		 * dfs puts edge labels at bottom and want only
		 * real nodes at bottom, try to correct that.
		 */
		spn = splay_tree_min(sp_parsedwnl);

		while (spn) {
			un = (struct unode *)spn->value;

			if (un->bitflags.edgelabel) {

				/* scan the outgoing edges connected to node */
				if (splay_tree_has_data(un->sp_poe)) {

					spn2 = splay_tree_min(un->sp_poe);

					while (spn2) {
						ue = (struct uedge *)spn2->value;

						if (ue->bitflags.reversed == 0) {

							/* XXX incoming edge */

							/* outgoing edge */
							if (ue->fn == un) {

								/* move node in level */
								if (ue->tn->level <= un->level) {
									ue->tn->level = un->level + (1 + 1 + levelextra);
									if (ue->tn->level > maxlevel) {
										maxlevel = ue->tn->level;
									}
								}

							}

						}

						spn2 = splay_tree_successor(un->sp_poe, spn2->key);
					}
				}

			}

			/* XXX need to rescan if there is a change.
			 * other edges and edgelabels todo. elab1
			 */
			spn = splay_tree_successor(sp_parsedwnl, spn->key);
		}
	}

	/* number of levels int the graph [1...n] */
	nlevels = (maxlevel + 1);

	if (option_ldebug > 1) {
		printf("%s(): graph has %d levels [0...%d]\n", __FUNCTION__, nlevels, maxlevel);
		fflush(stdout);
	}

	/* check horizontal edges */

	/* number of horizontal edges */
	he = 0;

	spn = splay_tree_min(sp_parsedwel);

	while (spn) {
		ue = (struct uedge *)spn->value;

		if (ue->fn->level == ue->tn->level) {

			if (option_ldebug || 0) {
				printf("%s(): edge number=[e%d] \"%s\"->\"%s\" is horizontal at level %d\n", __FUNCTION__,
				       ue->number, ue->fn->name, ue->tn->name, ue->fn->level);
				fflush(stdout);
			}

			he = (he + 1);
		}

		spn = splay_tree_successor(sp_parsedwel, spn->key);
	}

	if (option_ldebug > 1) {
		printf("%s(): graph has %d horizontal edges\n", __FUNCTION__, he);
		fflush(stdout);
	}

	return (he);
}

/* split long and horizontal edges with dummy nodes */
void longedges(void)
{
	splay_tree_node spn = (splay_tree_node) 0;
	struct unode *tmpnode = NULL;
	struct unode *tmpnode1 = NULL;
	struct unode *tmpnode2 = NULL;
	struct unode *tmpnode3 = NULL;
	int i = 0;
	int len = 0;
	int ee = 0;
	int le = 0;
	int he = 0;
	int re = 0;
	struct unode *prev = NULL;
	struct unode *dummy = NULL;
	struct unode *idnode = NULL;
	struct uedge *ue = NULL;
	struct uedge *uenew = NULL;
	struct uedge *uenew1 = NULL;
	struct uedge *uenew2 = NULL;
	struct uedge *uenew3 = NULL;
	struct uedge *uenew4 = NULL;
	struct unode *un = (struct unode *)0;
	int edgenum = 0;
	splay_tree sp_tmp = (splay_tree) 0;

	/* clear node id database */
	uniqnodeid_clear();

	/* scan the edge list for type of edge */
	spn = splay_tree_min(sp_parsedwnl);

	while (spn) {
		un = (struct unode *)spn->value;

		/* check part of edge list of node */
		if (splay_tree_has_data(un->sp_poe) == 0) {
			/* copy this single node */

			if (option_no_singlenodes) {
				/* skip singlenode */
			} else {
				uniqnodeid_add(un->number, un);
			}
		} else {
			/* node with connections */
			uniqnodeid_add(un->number, un);
		}

		/* next edge */
		spn = splay_tree_successor(sp_parsedwnl, spn->key);
	}

	/* clear counters */
	ee = 0;
	le = 0;
	he = 0;
	re = 0;

	/* build  a tmp copy */
	edgenum = 0;

	sp_tmp = splay_tree_new(splay_tree_compare_ints, NULL, NULL);

	/* scan the edge list for type of edge */
	spn = splay_tree_min(sp_parsedwel);

	while (spn) {
		ue = (struct uedge *)spn->value;

		/* skip invisible edges */
		if (ue->bitflags.visible == 0) {
			/* next edge */
			spn = splay_tree_successor(sp_parsedwel, spn->key);
			continue;
		}

		/* increment edge count */
		ee = (ee + 1);

		/* edge *must* point downwards in drawing */
		if (ue->tn->level < ue->fn->level) {

			/* */
			if (option_ldebug) {
				printf("%s(): edge number=[e%d] \"%s\"(level=[%d])->\"%s\"(level=[%d]) is not downwards, fixing\n",
				       __FUNCTION__, ue->number, ue->fn->name, ue->fn->level, ue->tn->name, ue->tn->level);
				fflush(stdout);
			}

			/* count long edges which should have been reversed */
			re = (re + 1);

			/* reverse this edge */
			tmpnode = ue->fn;
			ue->fn = ue->tn;
			ue->tn = tmpnode;

			/* toggle the edge reversed bit */
			if (ue->bitflags.reversed) {
				ue->bitflags.reversed = 0;
			} else {
				ue->bitflags.reversed = 1;
			}

		}

		if (abs(ue->tn->level - ue->fn->level) > 1) {
			/* count long edges */
			le = (le + 1);
		} else if (ue->tn->level == ue->fn->level) {
			/* count horizontal edges */
			he = (he + 1);
		} else {
			/* regular edge whith distance 1 level downwards */
			splay_tree_insert(sp_tmp, (splay_tree_key) edgenum, (splay_tree_value) spn->value);
			edgenum = (edgenum + 1);
		}

		/* next edge */
		spn = splay_tree_successor(sp_parsedwel, spn->key);
	}

	if (option_ldebug > 1) {
		printf("%s(): %d edges with %d long-edges, %d horizontal-edges and %d now-reversed-edges\n", __FUNCTION__, ee, le,
		       he, re);
		fflush(stdout);
	}

	if ((option_ldebug > 1) && (re > 0)) {
		printf("%s(): %d edges should have been reversed\n", __FUNCTION__, re);
		fflush(stdout);
	}

	/* check if edges needed to modify */
	if ((le + he) == 0) {
		/* no mods needed and copy the new numbered edgelist */
		splay_tree_delete(sp_parsedwel);
		sp_parsedwel = (splay_tree) 0;

		/* copy from tmp into new edgelist */
		if (splay_tree_has_data(sp_tmp)) {
			sp_parsedwel = splay_tree_new(splay_tree_compare_ints, NULL, NULL);

			spn = splay_tree_min(sp_tmp);

			while (spn) {
				/* copy tmp list as working edge list */
				splay_tree_insert(sp_parsedwel, (splay_tree_key) spn->key, (splay_tree_value) spn->value);

				spn = splay_tree_successor(sp_tmp, spn->key);
			}

		}

		/* wipe tmp data */
		splay_tree_delete(sp_tmp);
		sp_tmp = (splay_tree) 0;

		return;
	}

	/* split edges and build new current working edge list */

	/* scan the edge list for hor. type of edge */
	if (he) {

		spn = splay_tree_min(sp_parsedwel);

		while (spn) {
			ue = (struct uedge *)spn->value;

			/* skip invisible edges */
			if (ue->bitflags.visible == 0) {
				/* next edge */
				spn = splay_tree_successor(sp_parsedwel, spn->key);
				continue;
			}

			/* check horizontal edges */
			if (ue->tn->level != ue->fn->level) {
				/* next edge */
				spn = splay_tree_successor(sp_parsedwel, spn->key);
				continue;
			}

			/* split horizontal edge (ue->tn->level == ue->fn->level) with dummy node at next level */
			if (option_testcode || 0) {
				printf("%s(): horizontal edge number=[e%d] \"%s\"->\"%s\" level=[%d]\n", __FUNCTION__, ue->number,
				       ue->fn->name, ue->tn->name, ue->fn->level);
			}

			/* create the dummynode with uniq name */
			tmpnode1 = udummynode_new();

			/* put dummy node at next level */
			tmpnode1->level = (ue->fn->level + 1);

			/* update number of levels if needed */
			if (tmpnode1->level > maxlevel) {
				maxlevel = tmpnode1->level;
				nlevels = (maxlevel + 1);
			}

			/* mark this is a dummynode for horizontal edge at interleave level */
			tmpnode1->bitflags.dummynode = 1;
			tmpnode1->bitflags.horedge = 1;

			/* check if node is in database */
			idnode = uniqnodeid(tmpnode1->number);

			/* insert if not */
			if (idnode == NULL) {
				uniqnodeid_add(tmpnode1->number, tmpnode);
			}

			/* add as virtual node */
			virtualnl_add(tmpnode1);

			/* add dummynode to work on */
			parsedwnl_add(tmpnode1);

			/* create connecting edge 1 */
			uenew1 = uedge_new(ue->fn, tmpnode1);

			/* copy edge attributes */
			uedge_copy_attribs(ue, uenew1);

			/* mark this is edge in a horizontal edge */
			uenew1->bitflags.horedge = 1;
			uenew1->bitflags.visible = 1;

			/* add as virtual edge */
			virtualel_add(uenew1);

			/* add in edge list */
			splay_tree_insert(sp_tmp, (splay_tree_key) edgenum, (splay_tree_value) uenew1);

			edgenum = (edgenum + 1);

			/* create the dummynode with uniq name at level+2 beyond interleave level */
			tmpnode2 = udummynode_new();

			/* put dummy node at next level */
			tmpnode2->level = (ue->fn->level + 2);

			/* update number of levels if needed */
			if (tmpnode2->level > maxlevel) {
				maxlevel = tmpnode2->level;
				nlevels = (maxlevel + 1);
			}

			/* mark this is a dummynode for horizontal edge at interleave level */
			tmpnode2->bitflags.dummynode = 1;
			tmpnode2->bitflags.horedge = 1;

			/* check if node is in database */
			idnode = uniqnodeid(tmpnode2->number);

			/* insert if not */
			if (idnode == NULL) {
				uniqnodeid_add(tmpnode2->number, tmpnode);
			}

			/* add as virtual node */
			virtualnl_add(tmpnode2);

			/* add dummynode to work on */
			parsedwnl_add(tmpnode2);

			/* create connecting edge 2 */
			uenew2 = uedge_new(tmpnode1, tmpnode2);

			/* copy edge attributes */
			uedge_copy_attribs(ue, uenew2);

			/* mark this is edge in a horizontal edge */
			uenew2->bitflags.horedge = 1;
			uenew2->bitflags.visible = 1;

			/* add as virtual edge */
			virtualel_add(uenew2);

			/* todo in this hor. edge there are two incoming
			 * edges at tmpnode2 because next edges are reversed.
			 * then there is no outgoing edge at dummy node.
			 * this is to have all edges pointing downward
			 * but a hor. edge must be checked in followedge
			 * and drawing routines. better solution?
			 */

			/* add in edge list */
			splay_tree_insert(sp_tmp, (splay_tree_key) edgenum, (splay_tree_value) uenew2);

			edgenum = (edgenum + 1);

			/* create the dummynode with uniq name */
			tmpnode3 = udummynode_new();

			/* put dummy node at next level */
			tmpnode3->level = (ue->fn->level + 1);

			/* update number of levels if needed */
			if (tmpnode3->level > maxlevel) {
				maxlevel = tmpnode3->level;
				nlevels = (maxlevel + 1);
			}

			/* mark this is a dummynode for horizontal edge at interleave level */
			tmpnode3->bitflags.dummynode = 1;
			tmpnode3->bitflags.horedge = 1;

			/* check if node is in database */
			idnode = uniqnodeid(tmpnode3->number);

			/* insert if not */
			if (idnode == NULL) {
				uniqnodeid_add(tmpnode3->number, tmpnode);
			}

			/* add as virtual node */
			virtualnl_add(tmpnode3);

			/* add dummynode to work on */
			parsedwnl_add(tmpnode3);

			/* create connecting edge from level+1 to level+2 */
			uenew3 = uedge_new(tmpnode3, tmpnode2);

			/* copy edge attributes */
			uedge_copy_attribs(ue, uenew3);

			/* mark this is edge in a horizontal edge */
			uenew3->bitflags.horedge = 1;
			uenew3->bitflags.reversed = 1;
			uenew3->bitflags.visible = 1;

			/* add as virtual edge */
			virtualel_add(uenew3);

			/* add in working edge list */
			splay_tree_insert(sp_tmp, (splay_tree_key) edgenum, (splay_tree_value) uenew3);

			edgenum = (edgenum + 1);

			/* create connecting edge */
			uenew4 = uedge_new(ue->tn, tmpnode3);

			/* copy edge attributes */
			uedge_copy_attribs(ue, uenew4);

			/* mark this is edge in a horizontal edge */
			uenew4->bitflags.horedge = 1;
			uenew4->bitflags.reversed = 1;
			uenew4->bitflags.visible = 1;

			/* add as virtual edge */
			virtualel_add(uenew4);

			/* add in working edge list */
			splay_tree_insert(sp_tmp, (splay_tree_key) edgenum, (splay_tree_value) uenew4);

			edgenum = (edgenum + 1);

			/* next edge */
			spn = splay_tree_successor(sp_parsedwel, spn->key);
		}

	}

	/* handle longer edges */
	if (le) {

		spn = splay_tree_min(sp_parsedwel);

		while (spn) {
			ue = (struct uedge *)spn->value;

			/* skip invisible edges */
			if (ue->bitflags.visible == 0) {
				/* next edge */
				spn = splay_tree_successor(sp_parsedwel, spn->key);
				continue;
			}

			/* check for longer edge then 1 level, skip hor. edges too. */
			if (abs(ue->tn->level - ue->fn->level) <= 1) {
				/* next edge */
				spn = splay_tree_successor(sp_parsedwel, spn->key);
				continue;
			}

			/* split long edge between multiple levels */
			len = abs(ue->tn->level - ue->fn->level);

			/* node to start long edge */
			prev = ue->fn;

			/* cut edge */
			for (i = 0; i < (len - 1); i++) {
				/* create new dummy node */
				dummy = udummynode_new();

				/* put this dummy node at next level */
				dummy->level = (prev->level + 1);

				/* indicate this is a dummynode part of a long edge */
				dummy->bitflags.dummynode = 1;
				dummy->bitflags.longedge = 1;

				/* check dummy node is in database */
				idnode = uniqnodeid(dummy->number);

				/* add to database */
				if (idnode == NULL) {
					uniqnodeid_add(dummy->number, dummy);
				}

				/* add as virtual node */
				virtualnl_add(dummy);
				parsedwnl_add(dummy);

				/* create connecting edge */
				uenew = uedge_new(prev, dummy);

				/* copy edge attributes */
				uedge_copy_attribs(ue, uenew);

				/* mark this is edge in a long edge */
				uenew->bitflags.longedge = 1;
				uenew->bitflags.visible = 1;

				/* add as virtual edge */
				virtualel_add(uenew);

				/* add edge to work list */
				splay_tree_insert(sp_tmp, (splay_tree_key) edgenum, (splay_tree_value) uenew);

				edgenum = (edgenum + 1);

				/* done and make now the end node as start node for the next edge */
				prev = dummy;
			}

			/* terminate the chain of split edges with edge to the original to node */

			/* create connecting edge */
			uenew = uedge_new(prev, ue->tn);

			/* copy edge attributes */
			uedge_copy_attribs(ue, uenew);

			/* mark this is edge in a long edge */
			uenew->bitflags.longedge = 1;
			uenew->bitflags.visible = 1;

			/* add as virtual edge */
			virtualel_add(uenew);

			/* add edge to work list */
			splay_tree_insert(sp_tmp, (splay_tree_key) edgenum, (splay_tree_value) uenew);

			edgenum = (edgenum + 1);

			/* next edge */
			spn = splay_tree_successor(sp_parsedwel, spn->key);
		}
	}

	/* copy the new numbered edgelist */
	splay_tree_delete(sp_parsedwel);
	sp_parsedwel = (splay_tree) 0;

	/* copy from tmp into new edgelist */
	if (splay_tree_has_data(sp_tmp)) {
		sp_parsedwel = splay_tree_new(splay_tree_compare_ints, NULL, NULL);

		spn = splay_tree_min(sp_tmp);

		while (spn) {
			splay_tree_insert(sp_parsedwel, (splay_tree_key) spn->key, (splay_tree_value) spn->value);
			spn = splay_tree_successor(sp_tmp, spn->key);
		}

	}

	/* wipe tmp data */
	splay_tree_delete(sp_tmp);
	sp_tmp = (splay_tree) 0;

	return;
}

/* */
static void folding_all_subg(struct usubg *subg, int foldbit)
{
	splay_tree_node spn = (splay_tree_node) 0;
	struct usubg *sg = (struct usubg *)0;

	/* set the new folding status */
	subg->bitflags.folded = foldbit;

	/* scan subgraphs in this subgraph */
	if (splay_tree_has_data(subg->sp_sg)) {

		spn = splay_tree_min(subg->sp_sg);
		while (spn) {
			sg = (struct usubg *)spn->value;
			/* recurse into sub sub ... graph */
			folding_all_subg(sg, foldbit);
			spn = splay_tree_successor(subg->sp_sg, spn->key);
		}

	}

	return;
}

/* fold or unfold all subgraphs at once 0=unfold 1=fold */
void folding_all(int status)
{
	int foldbit = 0;
	splay_tree_node spn = (splay_tree_node) 0;
	struct usubg *sg = (struct usubg *)0;
	/* set folding bit status */
	if (status) {
		foldbit = 1;
	} else {
		foldbit = 0;
	}

	/* scan the subgraphs from input */
	if (splay_tree_has_data(sp_parsedsgl)) {

		spn = splay_tree_min(sp_parsedsgl);
		while (spn) {
			sg = (struct usubg *)spn->value;
			folding_all_subg(sg, foldbit);
			spn = splay_tree_successor(sp_parsedsgl, spn->key);
		}

	}

	return;
}

/* end */
